package com.leetcode.动态规划.买卖股票的最佳时机;

public class L123买卖股票的最佳时机III {
	public static void main(String[] args) {
		int result = maxProfit(new int[] {1,2,4,2,5,7,2,4,9,0});
		System.out.println(result);
	}

	public static int maxProfit(int[] prices) {
		int len = prices.length;
		/**
		 * dp[i][0]:表示第i天无操作
		 * -dp[i][1]:表示第i天或之前第一次买入所得的最大现金
		 * ->有两种状态：1、第i天之前已经买入，则延续前一天买入的现金dp[i][1] = dp[i - 1][0]
		 * 			  2、第i天买入，则之前没有买入，dp[i][1] = dp[i - 1][0] - prices[i]
		 * 			  取两者最大。
		 * -dp[i][2]:表示第i天或之前第一次卖出所得的最大现金
		 * ->有两种状态：1、第i天之前卖出，则延续前一天卖出的现金dp[i][2] = dp[i - 1][2]
		 * 			  2、第i天卖出，则dp[i][2]=dp[i - 1][1](前一天没入的状态) + prices[i]
		 * 			取两者最大。
		 * 同理可以推出dp[i][3]和dp[i][4]。
		 * dp[i][3]:表示第i天或之前第二次买入所得的最大现金
		 * dp[i][4]:表示第i天或之前第二次卖出所得的最大现金
		 */
		int[][] dp = new int[len][5];
		dp[0][1] = dp[0][3] = -prices[0];
		for(int i = 1;i < len;i++) {
			dp[i][0] = dp[i - 1][0];
			dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
			dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
			dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
			dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
		}
		return dp[len - 1][4];
	}
}
